Programmable logic devices, such as a complex programmable logic device (CPLD), typically include a number of independent logic blocks interconnected by a global or centralized routing structure. For example, FIG. 1 illustrates a block diagram of a conventional CPLD 10 that includes a routing structure 100 and sixteen logic blocks 102, with each logic block 102 having 16 macrocells (not illustrated) and receiving 36 inputs from routing structure 100. Each logic block 102 in CPLD 10 includes a programmable AND array (not illustrated) that a user configures to provide product term outputs of the true and complement form of the logical inputs received from routing structure 100. The product terms may be summed and the resulting sum of product terms registered in the macrocells within each logic block 102. The number of logical inputs that may factor into each product term is referred to as the “input width” for a given logic block and is fixed by the routing structure configuration. With respect to FIG. 1, the input width for logic blocks 102 is thirty-six. Another metric for a logic block is its logic depth, which is determined by the number of product terms that may be summed and registered within each macrocell.
Users often require relatively wide input logic blocks providing a high density of macrocells to implement complex functions such as decoders. However, as just described, conventional CPLD logic blocks are implemented with a fixed input width such that users may achieve a higher input width only by cascading product terms through the routing structure. However, this cascading through the 10, routing structure introduces routing delays and limits the maximum-achievable input width. To provide enhanced product term cascading, U.S. Ser. No. 10/133,016 describes a programmable device wherein product terms may be directly cascaded from one logic block to another to increase the input width without passing through the routing structure. A high-level block diagram for two logic blocks within such a programmable device 200 is shown in FIG. 2.
Logic blocks within programmable device 200 may be organized into feeder logic blocks 205 and receiver logic blocks 210. In the exemplary embodiment shown in FIG. 2, each logic block 205 and 210 receives 68 input signals from a routing structure 220. Each logic block 205 and 210 contains the same number of product term circuits 230 and thus each has the same number of product term outputs. Ten product term outputs pt_f0 through pt_f9 and pt_r0 through pt_r9 are shown for logic block 205 and 210, respectively. Each logic block 205 and 210 contains macrocells (not illustrated) for registering sums of the product term outputs. In the embodiment illustrated, each macrocell may register the sum of five product term outputs. Thus, the product term outputs may be organized according to which macrocell they correspond to. For example, product term outputs pt_f0 through pt_f4 may be summed at macrocell 0 in feeder logic block 205. For illustration clarity, additional product term outputs (and their corresponding product term circuits and macrocells) for each logic block are not shown.
To facilitate product term cascading, receiver logic block includes a plurality of AND gates 240 corresponding on a one-to-one basis with the plurality of product term outputs. For example, one AND gate 240 receives pt_r0 and pt_f0, another AND gate 240 receives pt_r1 and pt_f1, and so on. Each AND gate 240 is configured to always receive the corresponding product term output from receiver logic block 210. However, the product term outputs from feeder logic block 205 are selectively fused into AND gates 240 through the activation of fuse points 250. If a fuse point is not activated, the corresponding input for AND gate 240 is tied to a “true” logic level. Because the AND of a true value with another input will depend solely upon the logical state of the other input, an output 260 of an AND gate 240 will simply reflect the value of the corresponding receiver logic block product term output if its fuse point 250 is not activated. If, however, a fuse point 250 is activated, output 260 will be the AND (or logical product) of both the corresponding receiver and feeder logic block product term outputs. Note the advantages provided by such a product term cascading. Because the feeder block product term output is not cascaded through routing structure 220, a logical input for receiver logic block 210 need not be occupied by the cascaded product term. Moreover, the routing delay and routing burden associated with cascading through routing structure 220 is avoided.
Despite the advantages provided by the product term cascading approach discussed with respect to FIG. 2, issues arise with respect to the assignment of input variables between feeder logic block 205 and receiver logic block 210. Each AND gate output 260 is a product term having a maximum width of twice whatever the routing-structure-defined-maximum input width is for each cascaded product term. In the embodiment illustrated in FIG. 2, this routing-structure-limited input width is 68 logical input variables. Suppose a user's design requires a product term having an input width of 100 logical variables. Because this width exceeds the maximum number of logical variables (68) that can be provided by the routing structure 220 to any one logical block, product term cascading is required. In such a case, however, an assignment choice must be made between feeder logic block 205 and receiver logic block 210. In other words, the 100 input variables must be split between receiver logic block 210 and feeder logic block 205. This split may be better understood with the following example: Let f be a logic function in a sum of n products term form, where each product term may have a width of k inputs, k being larger than the routing-structure-limited input width for each logic block. Thus, the function f may be represented by the equation f=pt0+pt1+ . . . +ptn. Splitting the inputs for each product term in this function may be illustrated by reformulating the function as f=(pt_r0*pt_f0)+(pt_r1*pt_f1)+ . . . +(pt_rn*pt_fn), where pt_ri are the product term outputs of receiver logic block 210 and pt_fi are the product term outputs of the feeder logic block 210 as discussed with respect to FIG. 2. Note that any given product term pt_fi or pt_ri may be held constant to “true” or logical one if it supplies no input variables. If a product term output from receiver logic block 210 supplies no input variables, it is effectively wasted. However, the number of product term outputs required from receiver logic block 210 to form function f is determined by the integer number n and cannot be changed. Thus, one approach to prevent the wastage of product term outputs in receiver logic block 210 is to assign the maximum number of logical inputs (as defined by the routing structure limitations) to receiver logic block 210 and minimize the number assigned to feeder logic block 205. For example, with respect to the embodiment shown in FIG. 2, if function f has a width k of 70 input variables, this approach would apportion 68 input variables to receiver logic block 210 and only 2 to feeder logic block 205. While such an approach prevents the wastage of product terms, it leads to routing burdens in that routing structure 210 must then provide for its maximum allowable number of inputs to receiver logic block 210.
In sum, although the direct width cascading discussed with respect to FIG. 2 allows a receiver logic block to borrow inputs from a feeder logic block to thereby achieve greater product term input width, the associated product term cascading may lead to wastage of product terms or routing structure burdens. Accordingly, there is a need in the art for an efficient approach to partition inputs between logic blocks providing product term cascading to increase input width.